package leetcode_600;

/**
 *@author 周杨
 *ArrayNesting_565 深度优先遍历 
 *describe:用visited数组记录遍历过的元素 AC 48%
 *2018年9月16日 下午1:40:42
 */
public class ArrayNesting_565 {
	public int arrayNesting(int[] nums) {
		 if(nums.length==0)
			return 0;
	     boolean visited[]=new boolean [nums.length];
	     int res=0;
	     int count=0;//count==nums.length立即剪枝
	     for(int i=0;i<nums.length;++i) {
	    	 if(count==nums.length)
	    		 return res;
	    	 int index=i;
	    	 int now=0;
	    	 while(!visited[index]) {
	    		 visited[index]=true;
	    		 ++count;
	    		 ++now;
	    		 index=nums[index];
	    	 }
	    	 res=Math.max(res, now);
	     }
	     return res;
	}
}
